57. 插入区间

// 给你一个 无重叠的 ，按照区间起始端点排序的区间列表。
// 在列表中插入一个新的区间，你需要确保列表中的区间仍然有序且不重叠（如果有必要的话，可以合并区间）。
var insert = function(intervals, newInterval) {
  if (intervals.length === 0) return [newInterval];
  const arr = [];
  let [left, right] = newInterval;
  let placed = false;
  for (let i = 0; i < intervals.length; i++) {
    const cur = intervals[i];
    // 当前数组左侧大于插入数组的最大值, 插入数组在当前数组的左侧
    if (cur[0] > right) {
      if (!placed) {
        arr.push([left, right]);
        placed = true;
      }

      arr.push(cur);
    } else if (cur[1] < left) {
      // 当前数组最大值小于插入数组最小值, 插入数组在右侧, 不用管
      arr.push(cur);
    } else {
      // 有交集
      left = Math.min(left, cur[0]);
      right = Math.max(right, cur[1]);
    }
  }
  if (!placed) arr.push([left, right]);
  return arr;
};
console.log(
  insert(
    [
      [1, 3],
      [6, 9],
    ],
    [2, 5]
  )
); // [[1,5],[6,9]]
console.log(
  insert(
    [
      [1, 2],
      [3, 5],
      [6, 7],
      [8, 10],
      [12, 16],
    ],
    [4, 8]
  )
); // [[1,2],[3,10],[12,16]]